#include <stdio.h>
#include <stdlib.h>
#define MAX_LEN 30

typedef int ElemType;
typedef struct TreeNode { /*二叉树结点结构*/
    ElemType Data;
    struct TreeNode *Left;
    struct TreeNode *Right;
}BTNode, *BinTree;

typedef struct InfoNode{ /*输入信息封装结构*/
    /*由Post序列和In序列唯一确定二叉树*/
    ElemType *Post;
    ElemType *In;
    int l, r, L, R; /*l,r为Post左右边界，L,R为In左右边界*/
}InfoNode, *PtrToInfo;

PtrToInfo GetLeftInfo(PtrToInfo info){
    int pos;
    PtrToInfo ret=(PtrToInfo)malloc(sizeof(InfoNode));
    if(!ret) printf("ret: malloc error!\n");
    ret->Post = info->Post; /*继承信息*/
    ret->In   = info->In;
    for(pos=0; pos<=info->R; pos++){ /*在In序列中找根结点的左子树序列段*/
        if(info->In[pos] == info->Post[info->r]){
            break; /*找到Post序列尾元素在In序列中的位置*/
        }
    }
    ret->L = info->L; ret->R = pos-1; /*在In序列中由根结点划分出左右子树*/
    ret->l = info->l; ret->r = ret->l+(ret->R-ret->L); /*由Post序列中的左右子树确定In序列中的左右子树*/

    return ret;
}
PtrToInfo GetRightInfo(PtrToInfo info){
    int pos;
    PtrToInfo ret=(PtrToInfo)malloc(sizeof(InfoNode));
    if(!ret) printf("ret: malloc error!\n");
    ret->Post = info->Post;
    ret->In   = info->In;
    for(pos=0; pos<=info->R; pos++){
        if(info->In[pos] == info->Post[info->r]){
            break;
        }
    }
    ret->L = pos+1; ret->R = info->R;
    ret->l = info->r-(ret->R-ret->L+1); ret->r = info->r-1;

    return ret;
}

BinTree BuildBT(PtrToInfo info){ /*由后序与中序序列确定二叉树*/
    /*递归地找到每个子树的根结点并与父结点相连即可建立二叉树*/
    BinTree root=NULL;

    if(info->l <= info->r){
        root = (BinTree)malloc(sizeof(BTNode));
        root->Data = info->Post[info->r]; /*确定根结点的值*/
        root->Left  = BuildBT(GetLeftInfo(info));/*递归：确定根结点的左链*/
        root->Right = BuildBT(GetRightInfo(info));/*递归：确定根结点的右链*/
    }
    /*else: root为NULL，递归出口*/
    return root;
}

void PreoderPrint(BinTree BT){
    if(BT){
        printf(" %d", BT->Data);
        PreoderPrint(BT->Left);
        PreoderPrint(BT->Right);
    }
}

int main(void){
    int N, i;
    BinTree T=NULL;
    PtrToInfo info=(PtrToInfo)malloc(sizeof(InfoNode));
    info->Post = (ElemType *)malloc(MAX_LEN*sizeof(ElemType));
    info->In   = (ElemType *)malloc(MAX_LEN*sizeof(ElemType));

    scanf("%d", &N);
    for(i=0; i<N; i++){
        scanf("%d", &info->Post[i]);
    }
    for(i=0; i<N; i++){
        scanf("%d", &info->In[i]);
    }
    info->l = info->L = 0;
    info->r = info->R = N-1;
    T = BuildBT(info);
    printf("Preorder:");
    PreoderPrint(T);

    return 0;
}